UVa/705 - Slash maze/705.4.cpp

   1 #include <iostream>
   2
   3 using namespace std;
   4
   5 int g[226][226];
   6 bool visited[226][226];
   7
   8 int r, c;
   9 bool cycle;
  10
  11 //#define DEBUG
  12
  13 typedef pair<int, int> node;
  14
  15 int di[] = { 0, +1,  0, -1};
  16 int dj[] = {+1,  0, -1,  0};
  17
  18 int shoot(const node &u, const node &dad, const node &start){
  19
  20   int cuenta = 1;
  21   int i = u.first, j = u.second;
  22
  23   visited[i][j] = true;
  24   //printf("Shooting (%d,%d)\n", i, j);
  25   bool probable = false;
  26   for (int k=0; k<4; ++k){
  27     int ni = i + di[k];
  28     int nj = j + dj[k];
  29
  30     //printf(" Objetivo: (%d,%d)\n", ni, nj);
  31
  32     //printf("r y c son: %d, %d\n", r, c);
  33
  34     if (0 <= ni && ni < 3*r &&
  35         0 <= nj && nj < 3*c &&
  36         g[ni][nj] != -1){
  37
  38       if (!visited[ni][nj]){
  39         cuenta += shoot(node(ni, nj), u, start);
  40       }else if (node(ni, nj) == start && node(ni, nj) != dad){
  41         probable = true;
  42       }
  43     }
  44   }
  45   if (probable && cuenta == 1){
  46     cycle = true;
  47   }
  48   return cuenta;
  49 }
  50
  51
  52 int main(){
  53   int mazeNo = 1;
  54   while ( cin >> c >> r && r && c){
  55
  56     for (int i=0; i<3*r; ++i) for (int j=0; j<3*c; ++j){ visited[i][j] =  g[i][j] = 0; }
  57
  58     for (int i=0; i<r; ++i){
  59       for (int j=0; j<c; ++j){
  60         char d;
  61         cin >> d;
  62         if (d == '\\'){
  63           g[3*i][3*j] = g[3*i+1][3*j+1] = g[3*i+2][3*j+2] = -1;
  64         }else if (d == '/'){
  65           g[3*i][3*j+2] = g[3*i+1][3*j+1] = g[3*i+2][3*j] = -1;
  66         }
  67       }
  68     }
  69
  70
  71 #ifdef DEBUG
  72     for (int i=0; i<3*r; ++i){
  73       for (int j=0; j<3*c; ++j){
  74         printf("%3d", g[i][j]);
  75       }
  76       cout << endl;
  77     }
  78     cout << endl;
  79     #endif
  80
  81     int longest = -9999999;
  82
  83     int count = 0;
  84     for (int i=0; i<3*r; ++i){
  85       for (int j=0; j<3*c; ++j){
  86         if (g[i][j] != -1 && !visited[i][j]){
  87
  88           //printf("Shooting (%d,%d)\n", i, j);
  89
  90           cycle = false;
  91           int dist = shoot(node(i, j), node(-1,-1), node(i, j));
  92           //cout << "Cycle of length " << dist << " found.\n";
  93           if (cycle){
  94             longest >?= dist;
  95             ++count;
  96           }
  97         }
  98       }
  99     }
 100
 101     #ifdef DEBUG
 102     for (int i=0; i<3*r; ++i){
 103       for (int j=0; j<3*c; ++j){
 104         printf("%3d", g[i][j]);
 105       }
 106       cout << endl;
 107     }
 108     cout << endl;
 109     #endif
 110
 111     printf("Maze #%d:\n", mazeNo++);
 112     if (count > 0){
 113       printf("%d Cycles; the longest has length %d.\n", count, longest/3);
 114     }else{
 115       printf("There are no cycles.\n");
 116     }
 117
 118     cout << endl;
 119   }
 120   return 0;
 121 }